import com.sun.org.apache.bcel.internal.generic.LADD;
import com.sun.org.apache.regexp.internal.RE;

import java.util.Stack;

public class MyQueue {


    //用栈实现队列
    // 用俩个栈
    // 栈s1 , 栈s2
    // 入栈就用s1 , 出栈就用s2
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop() {
        if (empty1()){
            return -1;
        }
        if(stack2.empty()){
            while (!stack1.empty()){
                stack2.push(stack1.pop());  //s2接收s1弹出的元素
            }
        }
        return stack2.pop();
    }

    public int peek1() {
        if (empty1()){
            return -1;
        }
        if(stack2.empty()){
            while (!stack1.empty()){
                stack2.push(stack1.pop());  //s2接收s1弹出的元素
            }
        }
        return stack2.peek();
    }

    public boolean empty1() {
        return stack1.empty() && stack2.empty();
    }

    //单链表实现队列
    static  class Node{
        public int val;
        public Node next;

        public Node(int val) {
            this.val = val;
        }
    }
    public Node head; //头节点
    public Node last; //尾节点

    public int useSide;
    //入队
    public void offer(int val){
        Node node = new Node(val);
        if (head == null){
            head = node;
            last = node;
        }else {
            //尾插入队
            last.next = node;
            last = node;
        }
        useSide++;
    }

    //出队
    public int poll(){
        if(empty()){
            //return -1;
            throw new QueueException("队列为空");
        }
        int ret = head.val;
        head = head.next;
        if(head == null){
            last = null; //只有一个节点的时候
        }
        useSide--;
        return ret;
    }
    public boolean empty(){
        return useSide == 0;
    }

//队列的peek

    public int peek(){
        if(empty()){
            return -1;
        }
        return head.val;
    }


    //队列的大小
    public int getUseSide(){
        return useSide;
    }
}
